#!/usr/bin/env python3
#-*- coding:utf-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2019年02月16日
描    述：
Copyright (C) 2019 All rights reserved.
'''
import sys
import math

class Solution:
    def numSquares(self, n: 'int') -> 'int':
        dp = [sys.maxsize for i in range(0, n +1)]
        for i in range(1, int(math.sqrt(n)) + 1):
            dp[i*i] = 1

        for i in range(1, n + 1):
            for j in range (1, int(math.sqrt(i)) + 1) :
                dp[i] = min(dp[i], dp[i - j * j] + 1)

        return dp[n]
